#ifndef _DYNAMICARRAY_H_
#define _DYNAMICARRAY_H_


namespace DARRAY
{
class DynamicArray
{
public:
    
    using ElementType = void*;
    DynamicArray();
    void SetFreePtr(void (*FreePtr)(ElementType) )
    {
        this->FreePtr = FreePtr;
    }
    void SetShowPtr(void (*ShowPtr)(ElementType))
    {   
        this->ShowPtr = ShowPtr;
    }
    void SetCompare(bool (*Compare)(ElementType,ElementType))
    {   
        this->Compare = Compare;
    }
    void SetCompareBig(bool (*CompareBig)(ElementType,ElementType))
    {   
        this->CompareBig = CompareBig;
    }
    void SetISCompare(bool (*IsCompare)(DynamicArray,DynamicArray))
    {   
        this->IsCompare = IsCompare;
    }
    // 尾插
    void InsertTail(const ElementType &element);   
    // 头插            
    void InsertHead(const ElementType &element);   
    // 中间插入法            
    void InsertByIndex(const ElementType &element, int index); 

    void show();
    DynamicArray(const DynamicArray &DArray);
    DynamicArray &operator=(const DynamicArray &DArray);
    //按下标查找
    ElementType FindByIndex(int index);
    ElementType& operator[](int index);
    //按值查找
    DynamicArray FindElement(const ElementType &element);
    //按下标删除
    void RemoveByIndex(int index);
    //按值删除
    void RemoveByElement(ElementType element);
    
    // int SearchElement(ElementType element);
     //按下标修改
    void UpdateByIndex(int index,const ElementType &element);
    //按值修改
    void UpdateByElement(const ElementType &oldValue,const ElementType &newValue);
    
    //排序：递归深度  2*log2n
    void Sort();
    //去重算法：去除数列中的相同值，只留一个
    void Duplicate();
    //合并两个有序数列
    DynamicArray Merge(const DynamicArray &a);
    //找交集
    DynamicArray FindInterSection(const DynamicArray &array);
    //找并集
    DynamicArray FindUnionSet(const DynamicArray &array);
    //找补集
    DynamicArray FindDifference(const DynamicArray &array);

    //判断两个数列是否相等
    bool operator==(const DynamicArray &array);

    int BinarySearch(const ElementType &element);

    //判断是不是一个子数列
    bool IsChild(const DynamicArray &array);
    //是否是连续子序列
    bool IsConChild(const DynamicArray &array);
    //获取一个子序列
    DynamicArray subsquence(int index,int len);

    ~DynamicArray();

    int Size();

private:
    void FastSort( int start, int end,int deepth,int MaxDepth);
    void InsertSort(int start ,int end);
    int Partition(int start,int end);
   
    ElementType *a;
    int capacity;
    int size;
    void (*FreePtr)(ElementType);
    void (*ShowPtr)(ElementType);
    bool (*Compare)(ElementType,ElementType);
    bool (*CompareBig)(ElementType,ElementType);
    bool (*IsCompare)(DynamicArray,DynamicArray);
};

}
#endif